#ifndef GRAPH_H_
#define GRAPH_H_

#include <boost/noncopyable.hpp>
#include <boost/optional/optional.hpp>
#include <iostream>

#include "graph_support/GraphSupport.h"

#include "graph_support/utils/PtrAccessOpSimulator.h"

namespace GRAPH_SUPPORT_NS
{

/**
 * this header file declare Graph interface which is used by algorithms
 * see VectorGraph implementation or Dinic, Dejkstra, MinCostFlow algorithms for details
 *
 * Graph implementations have to declare a number of types and implement a number of methods.
 * in order to check if the implementation is OK compile and run UniversalGraphTest.
 * if the test is OK, implementation is supposed to be OK to.
 *
 * [ about vertex types ]
 * Graph::GrVertex is a type of vertex. graph regularly copies objects of vertices
 * so if GrVertex is big and hard type,
 * use GrVertex * instead.
 * for example Graph::GrVertex = int - is OK, Graph::GrVertex = std::string - is not OK,
 * Graph::GrVertex = std::string * - is OK
 * see TestIntVertices, TestCharVertices, TestDistanceSearch for details.
 * TestBusinessGraph is not pretty example because it uses VectorGraph< BusinessObject >,
 * it is better to use VectorGraph< BusinessObject* > in this case
 *
 * Graph::Edge and Graph::EdgeAttributes allows to add any attributes to edges.
 * for example Dejkstra algorithm expects attributes to have a length.
 * and Dinic algorithm expects flow attributes.
 *
 * in contrast to vertices, edge objects aren't copied, Graph::GrEdge & type is used instead.
 * Graph::GrEdgePtr is apart marked type, it is not always true that Graph::GrEdgePtr == Graph::GrEdge * ,
 * see [ about iteration over edges ] for details.
 *
 * [ about access graph structure ]
 * There exist two approaches of access graph structure.
 * 1	the easiest one, uses defined by user vertex type ( Graph::GrVertex ) to iterate thru edges.
 * 		this mean doesn't make user to learn representation of the graph but performance of the mean
 * 		is not perfect.
 *
 * 2	more sophisticated then previous one. assigns for each edge unique size_t id. id-s are in range
 * 		[0 .. verticesCount - 1] so each id from the range has vertex prototype.
 * 		allows to store extra attributes for each vertex such as distance ( see Dejkstra ).
 *
 * 		see BaseGraph for details.
 *
 * [ about iteration over edges ]
 * since the goal was to create flexible library, graph_support was designed in such a way that graph
 * implementations set may be extended by users. moreover, it is possible to develop implicit
 * representations of graph. for example knight-on-chess-board-graph doesn't have to store all it's
 * edges (in contrast to MatrixGraph), it just has to know rules: how knight is able to walk.
 * see TestDinicAndKnightsWalking for details. It is expected that all implementations of standard
 * graph algorithms (like Dejkstra) are able to work with such implicit graphs.
 * consequently Graph can't give user proper GrEdge & because Graph implementations don't have to
 * store all edges and certain edge may be temporary object.
 * we use type GraphImpl::GrEdgePtr which represents pointer to GraphImpl::GrEdge
 * but it is not always true that GraphImpl::GrEdgePtr == GraphImpl::GrEdge *. GraphImpl::GrEdgePtr
 * has to overload operators * and -> in such a way that user is able to work with it like with real
 * pointer.
 * see interface of Graph::GrEdgeSynonim for details.
 * GraphImpl::GrEdgePtr is owned by
 * the graph and user shuldn't care about deleting GraphImpl::GrEdgePtr - s.
 *
 * GraphImpl::EdgeIterator - iterates over GraphImpl::GrEdgePtr
 *
 * NOTE: in code:
 * GraphImpl::GrEdgePtr eptr = * edgeIter;
 * GraphImpl::EdgeAttributes & attributes = eptr->getAttributes();
 * link attributes is guaranteed to be valid only while eptr is alive.
 */

/**
 * class Graph only declares necessary elements of graph interface.
 * there is no implementations here.
 */
class Graph : boost::noncopyable
{
/**
 * types declaration
 */
public:
	class GrVertex // no special requirements
	{
	};

	class EdgeAttributes
	{
	public:
		/**
		 * is expected to have default constructor.
		 */
		EdgeAttributes()
		{
		}
		/**
		 * processes event of edge creation, is empty in base class
		 */
		void onBidirEdgeCreated(
				EdgeAttributes & revertedAttributes,
				bool isOriginalEdge = true );
	};

	class GrEdge
	{
	public:
		const GrVertex beg() const;
		const GrVertex end() const;
		/**
		 * see [ about iteration over edges ]
		 */
		size_t begId() const;
		size_t endId() const;
	public:
		EdgeAttributes & getAttributes();
	};
	/**
	 * see [ about iteration over edges ]
	 */
	class GrEdgePtr
	{
	public:
		/**
		 * default is NULL
		 */
		GrEdgePtr();
		/**
		 * GrEdgePtr eptr = NULL;
		 */
		GrEdgePtr( int );
		GrEdge & operator * ();
		GrEdge * operator -> ();
	};

	class VertexIterator
	{
	public:
		// integration with std::{ for_each, find_if, ... }
		typedef int difference_type;
		typedef GrVertex value_type;
		typedef GrVertex * pointer;
		typedef GrVertex & reference;
		typedef std::forward_iterator_tag iterator_category;
	public:
		VertexIterator & operator ++ (); // only ++it, without it++
		bool operator != ( const VertexIterator & that ) const;
		GrVertex operator * ();
	private:
		typedef GrVertex * GrVertexPtr;
	public:
		/**
		 * here GrVertexPtr - is any type which has overloaded
		 * GrVertex * operator -> ()
		 * and
		 * GrVertex & operator * ().
		 * NOTE: for example use GrVertex * or utils::PtrAccessOpSimulator.
		 */
		GrVertexPtr operator -> ();
	};

	/**
	 * iterates over GrEdgePtr see [ about iteration over edges ]
	 */
	class EdgeIterator
	{
	public:
		// integration with std::{ for_each, find_if, ... }
		typedef int difference_type;
		typedef GrEdgePtr value_type;
		typedef GrEdgePtr * pointer;
		typedef GrEdgePtr & reference;
		typedef std::forward_iterator_tag iterator_category;
	public:
		const EdgeIterator & operator ++ ();
		bool operator != ( const EdgeIterator & that ) const;
		GrEdgePtr operator * ();
		GrEdgePtr * operator -> ();
	};

public:
	/**
	 * constructor is expected to have argument isBidirected
	 */
	Graph( bool isBidirected = false ) {}
	virtual ~Graph() {}

// access
public:
	size_t getVertexCount() const;
	/**
	 * iterates thru all vertices
	 */
	VertexIterator getVerticesBeg();
	VertexIterator getVerticesEnd();

	/**
	 * iterates thru edges of certain vertex
	 */
	EdgeIterator getEdgsBeg( const GrVertex & v );
	EdgeIterator getEdgsEnd( const GrVertex & v );
	/**
	 * FnT:
	 * fn( GrEdge & ) -- function which would be called for each out-edge
	 * dosn't allow to store GrEdges
	 */
	template< typename FnT >
	void forEachOutEdge( GrVertex v, const FnT & fn );
	// same via id-s
	EdgeIterator getEdgsBegId( size_t vid );
	EdgeIterator getEdgsEndId( size_t vid );
	/**
	 * see forEachOutEdge( GrVertex, FnT )
	 */
	template< typename FnT >
	void forEachOutEdgeId( size_t vid, const FnT & fn );
	static const size_t NOT_A_VERTEX_ID = static_cast< size_t >( -1 );

public:
	/**
	 * if no such vertex exists, returns NOT_A_VERTEX_ID
	 */
	size_t vert2num( const GrVertex & v ) const;
	GrVertex num2vert( size_t vid ) const;

public:
	void addEdge(
			const GrVertex & beg, const GrVertex & end,
			const EdgeAttributes & edgeAttrs = EdgeAttributes() );
};

}

/**
 * TODO:
 * 		1 play with: const T & t vs T t in function arguments and compare performance
 * 		2 in operator == ( ??Iterator ) -- add comparsion of owners -- 4 example only for debud build mode
 * 		3 const GrVertex end() const; -- const everywhere
 * 		4 ?? may be move wrapigraph 2 decorators
 *		5 in << GrEdgePtr * operator -> () >> -- return NULL -- implement
 *		6 in << void forEachOutEdge( GrVertex v, const FnT & fn ) >> does const really necessary ??
 */

#endif /* GRAPH_H_ */
